

/**
 * 
 * RBTree
 * 
 * An implementation of a Red Black Tree with
 * non-negative, distinct integer values
 * 
 */



public class RBTree {

  private RBNode nil = new RBNode();    //null node
  private RBNode dRoot = new RBNode(Double.POSITIVE_INFINITY);  //dummy root
  private int size = 0; //size of tree
  private int cnt = 0; //Color flips counter
  private RBNode min = nil;
  private RBNode max = nil;
  
  
  public RBTree(){//create new empty tree
  }
  

  /**
   * public boolean empty()
   * 
   * returns true if and only if the tree is empty
   * 
   * complexity: O(1), because complexity of isNil is O(1).
   *  
   */
  public boolean empty() {
    if (isNil(dRoot.left())) { //dummy root has no left child
    	return true;
    }
    return false;
  }
  
  
  
  /**
   * public boolean search(int i)
   * 
   * returns true if and only if the tree contains i
   * 
   * the complexity of this function equals to the
   * complexity of nodeSearch, which is O(log(n)).
   *  
   */
  public boolean search(int i)
  {
	if (empty()) { //tree is empty
		return false;
	}
	if (isNil(nodeSearch(dRoot.left(), i))) { //there's no node with i in the tree
		return false;
	} else { //node was found
		return true;
	}
  }
  
  /**
   * public RBNode nodeSearch(RBNode node, int i)
   * 
   * Searches for a node in the tree.
   * 
   * Input:
   * 	node = root from which the search will start
   * 	i = key of the node to be searched for
   * If it exists, returns a pointer to it.
   * If it doesn't exist, returns null.
   * 
   * Complexity: O(log(n)).
   * with each recursive call we go one level down the tree.
   * maximum possible run time is equal to maximum possible height of tree,
   * which is 2*black height of tree, i.e O(log(n)).
   * 
   */
  
  private RBNode nodeSearch(RBNode node, int i){
	  if (node.key() == i) { //node was found
		  return node;
	  }
	  
	  if (node.key() < i){ //the node we're searching for will be on the right sub-tree
		  if (isNil(node.right())) { //there's no right sub-tree
			  return nil;
		  }
		  return nodeSearch(node.right(), i); //search the right sub-tree for i
	  }
	  if (node.key() > i){ //the node we're searching for will be on the left sub-tree
		  if (isNil(node.left())) { //there's no left sub-tree
			  return nil;
		  }
		  return nodeSearch(node.left(), i); //search the left sub-tree for i
	  }
	  return nil;
  }

  /**
   * public int insert(int i)
   * 
   * inserts the integer i into the binary tree; the tree
   * must remain valid (keep its invariants).
   * the function returns the number of color flips, or 0 if i was already in the tree
   * 
   * the complexity of insert() is O(log(n)):
   * - the complexity of findInsertionPlace and dispatchFixInsert is O(log(n)).
   * - the complexity of all other methods called from insert() is O(1).
   * 
   */
   public int insert(int i) {
	  if (i<0) return 0;
	  cnt = 0; //Reset the color flips counter
	  if (empty()){ //Insert root if tree is currently empty
		  dRoot.setLeft(new RBNode(i, dRoot));
		  ++size;
		  min = dRoot.left();
		  max = dRoot.left();
		  return cnt;
	  } else {
		  RBNode insertionPlace = nil;
		  RBNode newNode = nil;
		  if (i >= min.key() && i <= max.key()){
			  insertionPlace = findInsertionPlace(i, dRoot.left()); //Look for insertion place in the tree
			  if (insertionPlace != nil) newNode = addNode(i, insertionPlace);
		  }
		  else if (i < min.key()) {
			  insertionPlace = min;
			  newNode = addNode(i, insertionPlace);
			  min = newNode;
		  }
		  else if (i > max.key()) {
			  insertionPlace = max;
			  newNode = addNode(i, insertionPlace);
			  max = newNode;
		  }
		  if (insertionPlace != nil){ //if the value is not in the tree, insert the node.
			  ++size;
			  if (newNode.parent().color().equals("red")) {
				  dispatchFixInsert(identifyFixInsert(newNode), newNode); //Fix the tree
			  }
		  }
	  }
	  return cnt;
   }
  
  /**
   * public void delete(int i)
   * 
   * deletes the integer i from the binary tree, if it is there;
   * the tree must remain valid (keep its invariants).
   * the function returns the number of color flips, or 0 if i was not in the tree
   * 
   * complexity is O(log(n)): 
   * - the complexity of nodeSearch(), successor(), and dispatchFixDelete() is O(log(n)).
   * - the complexity of all other methods called from delete() is O(1).
   * 
   */
   public int delete(int i)
   {
	   if (i<0) return 0;
	   cnt = 0;
	   
	   if (empty()) return cnt; //tree is empty
	   
	   //get the about to be deleted node
	   RBNode node = nil;
	   if (i == min.key()) node = min;
	   else if (i == max.key()) node = max;
	   else node = nodeSearch(this.dRoot.left(), i);
	   if (node.equals(this.nil)) return cnt;
	   --size;//value exists in tree, so reduce tree size by 1
	   if (this.size == 0) {//i is the only value in the tree
		   this.dRoot.setLeft(this.nil);
		   max = nil;
		   min = nil;
		   return cnt;
	   }
	   
	   RBNode successor;
	   //Check if node has two sons. if so - copy the successor's value to node delete the successor.
	   if (hasTwoSons(node)) {
		   successor = successor(node);
		   node.setKey(successor.key());
		   node = successor;
	   }
	   if (node == min){
		   min = successor(node);
	   }
	   if (node == max){
		   max = predecessor(node);
	   }
	   //Get node son, parent and sibling for future use
	   RBNode nodeSon = getOnlySon(node);
	   RBNode nodeParent = node.parent();
	   RBNode nodeSibling = sibling(node);
	   RBNode nodeSiblingFarSon = siblingFarSon(node);
	   RBNode nodeSiblingCloseSon = siblingCloseSon(node);
	   
	   //Delete node and link his son to his parent
	   deleteCurrentNode(node);
	   
	   //If node's color was red do nothing
	   if (node.color().equals("red")) {
		   return cnt;
	   }
	   
	   //If node's color was black and his son is red change son's color to black
	   if (node.color().equals("black") 
			   && nodeSon.color().equals("red")) {
		   flipColor(nodeSon);
		   return cnt;
	   }
	   
	   //if node's color was black and had no red son go through fix cases
	   String Case = identifyFixDelete(nodeParent,nodeSibling,nodeSiblingFarSon,nodeSiblingCloseSon);
	   dispatchFixDelete(Case,nodeParent,nodeSibling);
	   
	   return cnt;
   }
   

   /**
    * 
    * private void deleteCurrentNode(RBNode node)
    * 
    * Deletes node from the tree and links his son as a new son of node's parent.
    * Left or right son is decided based on what node was.
    * 
    * precondition:
    * 	node has one son or no sons.
    * postcondition:
    * 	node is removed from the tree
    * 
    * complexity: O(1), because the complexity of all methods called from 
    * deleteCurrentNode() is O(1).
    * 
    * @param node
    */
   
   private void deleteCurrentNode(RBNode node) {
	   
	   RBNode nodeSon = getOnlySon(node);
	   
	   RBNode parent = node.parent();
	   if (parent.left().equals(node)) { //node was a left son and so will be his son
		   parent.setLeft(nodeSon);
	   } else { //node was a right son and so will be his son
		   parent.setRight(nodeSon);
	   }
	   nodeSon.setParent(parent);
	   
   }
   
   /**
    * 
    * private RBNode getOnlySon(RBNode node)
    * 
    * Returns node's only son.
    * 
    * precondition:
    * 	node has at most one son
    * 
    * @param node
    * @return if node has 1 son - node's only son. otherwise nil.
    * 
    * complexity: O(1), because the complexity of isNil() is O(1).
    */
   
   private RBNode getOnlySon(RBNode node) {
	   
	   if (!isNil(node.left())) { //left son isn't nil
		   return node.left();
	   } else { //left son doesn't exist
		   return node.right();
	   }
	   
   }
   
   
   /**
    * 
    * private RBNode successor(RBNode node)
    * 
    * Returns the successor of node, if exists. Returns nil otherwise.
    * 
    * @param node
    * @return node's successor.
    * 
    * complexity: O(log(n)):
    * in the algorithm for finding the successor we move one step right
    * and an unknown number of steps left. the number of steps left is
    * limited by the height of the tree, which is O(log(n)).
    */

   private RBNode successor(RBNode node) {
	
	   if (!(node.right().equals(this.nil))) { //node has a right child
		  node = node.right(); //go one step right
		  while (!node.left().equals(this.nil)) //go left until you encounter the minimum element in the left subtree 
			  node = node.left();
		  return node;
	   } else {//node has no right child
		   while (node == node.parent().right()) //go to the parent while node is a right child
			   node = node.parent(); 
		   if (node.parent() == this.dRoot) { //the predecessor is supposedly dRoot => return null
			   return this.nil; 
		   }
		   else { //the successor is a node in the tree, return it
			   return node.parent(); 
		   }
	   }
}


   /**
    * 
    * private RBNode predecessor(RBNode node)
    * 
    * Returns the predecessor of node, if exists. Returns nil otherwise.
    * 
    * @param node
    * @return node's predecessor.
    * 
    * complexity: O(log(n)):
    * in the algorithm for finding the predecessor we move one step left
    * and an unknown number of steps right. the number of steps right is
    * limited by the height of the tree, which is O(log(n)).
    */


   private RBNode predecessor(RBNode node) {
	
	   if (!(node.left().equals(this.nil))) { //node has a left child
		  node = node.left();
		  while (!node.right().equals(this.nil)) //go all the way down right
			  node = node.right();
		  return node;
	   } else {//node has no left child
		   while (node == node.parent().left()) {//go to parent while node is a left child
			   node = node.parent();
			   if (node == this.dRoot) { //we got to the dummy root, node has no predecessor
				   return nil;
			   }
		   }
		   return node.parent(); //predecessor found
	   }
}
   
   
   
   
/**
    * 
    * private boolean hasTwoSons(RBNode node)
    * 
    *  Returns true if node has two sons, false otherwise.
    * 
    * Complexity - O(1)
    */
   
   private boolean hasTwoSons(RBNode node) {
	   
	   if ( (!node.right().equals(this.nil)) //has a right son
			   && (!node.left().equals(this.nil))) { //has a left son
		   return true;
	   } else {
		   return false;
	   }
   }
   
   
   /**
    * public int min()
    * 
    * Returns the smallest key in the tree, or -1 if the tree is empty
    * is empty, returns -1;
    * 
    * Complexity - O(1)
    * 
    */
   public int min()
   {
	   if (empty()) return -1; 
	   return min.key();
   }
   
   /**
    * public int max()
    * 
    * Returns the largest key in the tree, or -1 if the tree is empty
    * 
    * Complexity - O(1)
    */
   public int max() {
	   if (empty()) return -1;
	   return max.key();
   }
   
  /**
   * public int[] toIntArray()
   * 
   * returns an int[] array containing the values stored in the tree,
   * in ascending order. 
   * 
   * Complexity - O(n)
   * Converting balanced binary tree to an array is basically a series of successor() actions.
   * Amor(successor()) = O(1), hence series of those actions is O(n).
   * 
   */
  public int[] toIntArray()
  {
	 RBNode curr = min; //get a pointer to the minimum node, the first element in the array
	 
	 int[] outputArray = new int[size]; //create an array with the size of the tree
	 
	 for (int i=0;i<size;++i) { //build the array
		 outputArray[i] = curr.key();
		 curr = successor(curr);
	 }
	 return outputArray;
  }

   /**
    * public int size()
    * 
    * Returns the number of nodes in the tree.
    * 
    * precondition: none
    * postcondition: none
    * 
    * Complexity - O(1)
    */
   public int size()
   {
	   return this.size;
   }

   /**
    * public RBNode findInsertionPlace(int i)
    * 
    * Return a pointer to the father of the node we want to insert
    * if the value is already in the tree return nil 
    * 
    * precondition: none
    * postcondition: none
    * 
    * Complexity - O(logn)
    * We might need to go all the way down the tree, hence complexity equals its height
    * 
    */
   private RBNode findInsertionPlace(int i, RBNode node) {
	   if (node.key() < i) { //current node's key is smaller than the new node
		   if (isNil(node.right())) { //current node doesn't have a right son
			   return node; //insertion place found
		   }
		   else { //current node has a right son
			   return findInsertionPlace(i, node.right()); //search the right subtree for insertion place
		   }
	   }
	   
	   if (node.key() == i) { //node already exists in the tree
		   return nil;
	   }
	   
	   if (node.key() > i){ //current node's key is bigger than the new node
		   if (isNil(node.left())) { //current node doesn't have a left son
			   return node; //insertion place found
		   }
		   else {
			   return findInsertionPlace(i, node.left()); //search the left subtree for insertion place
		   }
	   }
	   return nil;
   }
   
   
   /**
    * 
    * @param node
    * @return true iff node is nil.
    * 
    * Complexity - O(1)
    */
   private boolean isNil(RBNode node){
	   if (node.key() == -1) { //nil nodes has a '-1' key
		   return true;
	   }
	   return false; //node.key() != -1
   }
   
   /**
    * 
    * private String identifyFixDelete(RBNode node)
    * 
    * Checks which case should be executed: "1","2b","2r","3","4"
    * 
    * Complexity - O(1)
    * Fixed set of tests
    * 
    */
   private String identifyFixDelete(RBNode parent, RBNode sibling, RBNode siblingFarSon, RBNode siblingCloseSon) {
	   //case 1
	   if (sibling.color().equals("red")) {
		   return "1";
	   }
	   
	   //case 2b
	   if (sibling.color().equals("black")
			   && parent.color().equals("black")
			   && siblingFarSon.color().equals("black")
			   && siblingCloseSon.color().equals("black")) {
		   return "2b";
	   }
	   
	   //case 2r
	   if (sibling.color().equals("black")
			   && parent.color().equals("red")
			   && siblingFarSon.color().equals("black")
			   && siblingCloseSon.color().equals("black")) {
		   return "2r";
	   }
	   
	   
	   //case 3
	   if (sibling.color().equals("black")
			   && siblingFarSon.color().equals("black")
			   && siblingCloseSon.color().equals("red")) {
		   return "3";
	   }
	   
	   //case 4
	   if (sibling.color().equals("black")
			   && siblingFarSon.color().equals("red")) {
		   return "4";
	   }
	   return null;
	   
   }
   
   /** 
    * 
    * private void dispatchFixDelete(String caseID, RBNode node)
    * 
    * Calls to a case fix function according to caseID.
    * 
    * Postcondition:
    * Tree is valid
    * 
    * Complexity - O(log(n)):
    * - complexity of deleteCase2bFix is O(log(n)).
    * - complexity of other methods called from dispatchFixDelete is O(1).
    * 
    */
   
   private void dispatchFixDelete(String caseID, RBNode parent, RBNode sibling) {
	   if (caseID.equals("1")) {
		   deleteCase1Fix(parent,sibling);
	   }
	   
	   if (caseID.equals("2b")) {
		   deleteCase2bFix(parent,sibling);
	   }
	   
	   if (caseID.equals("2r")) {
		   deleteCase2rFix(parent,sibling);
	   }
	   
	   if (caseID.equals("3")) {
		   deleteCase3Fix(parent,sibling);
	   }
	   
	   if (caseID.equals("4")) {
		   deleteCase4Fix(parent,sibling);
	   }
   }
   
   
   

   /**
    * 
    * private RBNode siblingFarSon(RBNode node)
    * 
    * Returns a pointer to node's sibling's far son.
    * If node is a left son then sibling's far son is its right son.
    * If node is a right son then sibling's far son is its left son.
    * 
    * Returns nil is sibling has no far son.
    * 
    * Complexity - O(1)
    * 
    */
   
   private RBNode siblingFarSon(RBNode node) {
	   if (node.parent().left() == node) { //node is a left son
		   return node.parent().right().right();
	   } else { //node is a right son
		   return node.parent().left().left();
	   }
   }
   
   /**
    * 
    * private RBNode siblingFarSon(RBNode node)
    * 
    * Returns a pointer to node's sibling's close son.
    * If node is a left son then sibling's close son is its left son.
    * If node is a right son then sibling's close son is its right son.
    * 
    * Returns nil is sibling has no far son.
    * 
    * Complexity - O(1)
    * 
    */
   
   private RBNode siblingCloseSon(RBNode node) {
	   if (node.parent().left()==node) { //node is a left son
		   return node.parent().right().left();
	   } else { //node is a right son
		   return node.parent().left().right();
	   }
   }
   
   
   /**
    * 
    * private RBNode sibling(RBNode node)
    * 
    * Returns a pointer to the sibling to node if exists, nil otherwise
    * 
    * Complexity - O(1)
    * 
    */
   
   private RBNode sibling(RBNode node){
	   
	   RBNode parent = node.parent();
	   
	   if (parent.left().equals(node)) { //node is a left child
		   return parent.right(); //return right child
	   } else { //node is a right child
		   return parent.left(); //return left child
	   }
	   
   }
   
   
   /**
    * private void rightRotate(String rotateType, RBNode node)
    * 
    * Performs a left or right rotate when 'node' is the root of the sub-tree we're rotating.
    * 
    * precondition: 
    * 	1. (rotateType == 'left') $implies node has a right child 
    * 	2. (rotateType == 'right') $implies node has a left child
    * postcondition: sub-tree is rotated left or right, according to input
    * 
    * Complexity - O(1)
    * 
    */
   private void rotate(String rotateType, RBNode node) {
	   
	   if (rotateType == "right") { //Perform right rotate
		   RBNode X = node;
		   RBNode p = X.parent();
		   RBNode Y = X.left();
		   RBNode B = Y.right();
		   
		   //Switch places
		   if (X == p.left()) p.setLeft(Y);
		   else p.setRight(Y);
		   Y.setParent(X.parent());
		   X.setParent(Y);
		   B.setParent(X);
		   X.setLeft(B);
		   Y.setRight(X);
		   
	   } else { //Perform left rotate
		   
		   RBNode X = node;
		   RBNode p = X.parent();
		   RBNode Y = X.right();
		   RBNode B = Y.left();
		   
		   
		   //Switch places
		   if (X == p.left()) p.setLeft(Y);
		   else p.setRight(Y);
		   Y.setParent(X.parent());
		   X.setParent(Y);
		   B.setParent(X);
		   X.setRight(B);
		   Y.setLeft(X);
		
	   }

	   
	   
   }
   
   
   
   
   /**
    *  parent is colored red, sibling is colored black, rotate parent-sibling,
    *  and solve black height problem again.
    *  
    *  Complexity - O(1)
    *  	1. Fixed set of changes
    *  	2. Recursively fix the parent with O(1) fixes (Not 2b)
    * 
    */
   private void deleteCase1Fix(RBNode parent, RBNode sibling) {
	   flipColor(parent);
	   flipColor(sibling);
	   String dir = "";//indicates the direction of the rotation that we will perform
	   RBNode newSibling; //will be the sibling node after rotation
	   RBNode newSiblingFarSon;
	   RBNode newSiblingCloseSon;
	   if (sibling == parent.left()) {
		   dir = "right";
		   newSibling = sibling.right();
		   newSiblingFarSon = newSibling.left();
		   newSiblingCloseSon = newSibling.right();
	   }
	   else {
		   dir = "left";
		   newSibling = sibling.left();
		   newSiblingFarSon = newSibling.right();
		   newSiblingCloseSon = newSibling.left();
	   }
	   rotate(dir, parent);
	   String Case = identifyFixDelete(parent, newSibling, newSiblingFarSon, newSiblingCloseSon);
	   dispatchFixDelete(Case, parent, newSibling); //does not reach case 2b, so complexity is O(1).
   }
   
   /**
    *  sibling is colored red, and we solve black height problem of the parent.
    *  
    *  Complexity:  O(logn)
    *  	1. Fixed set of changes
    *  	2. Recursive call for fixing the parent - O(logn) - up to the root
    * 
    */
   private void deleteCase2bFix(RBNode parent, RBNode sibling) {
	   flipColor(sibling);
	   if (parent.parent() == dRoot) return;
	   RBNode newParent = parent.parent(); //the new node whose son's black height is too small.
	   RBNode newSibling = sibling(parent); //the new node whose sibling's black height is too small.
	   RBNode newSiblingFarSon;
	   RBNode newSiblingCloseSon;
	   if (newSibling == newParent.right()){
		   newSiblingCloseSon = newSibling.left();
		   newSiblingFarSon = newSibling.right();
	   }
	   else {
		   newSiblingCloseSon = newSibling.right();
		   newSiblingFarSon = newSibling.left();
	   }
	   String Case = identifyFixDelete(newParent, newSibling, newSiblingFarSon, newSiblingCloseSon);
	   dispatchFixDelete(Case, newParent, newSibling); //Case may be 2b again, so we may "2b" all the way up the tree.
   }
   
   /**
    * flip colors of sibling and sibling's close son, rotate between sibling and its
    * close son, activate deleteCase4Fix.
    * 
    * Complexity - O(1)
    * 	1. Fixed set of changes
    * 	2. Call case 4 fix which is O(1)
    * 
    */
   private void deleteCase3Fix(RBNode parent, RBNode sibling) {
	   flipColor(sibling);
	   String dir = "";//indicates the direction of the rotation that we will perform
	   RBNode siblingsCloseSon = new RBNode();
	   //will be the son of the node whose sibling's height will be 
	   //too small after rotation, on the side closer to the sibling.
	   if (sibling == parent.right()) {
		   siblingsCloseSon = sibling.left();
		   dir = "right";
	   }
	   else {
		   siblingsCloseSon = sibling.right();
		   dir = "left";
	   }
	   flipColor(siblingsCloseSon);
	   rotate(dir, sibling);
	   deleteCase4Fix(parent, siblingsCloseSon); //complexity is O(1)
   }
   
   /**
    * sibling gets parent's color, parent and sibling's far son are colored black,
    * rotate between parent and sibling
    * 
    * Complexity: O(1).
    */
   private void deleteCase4Fix(RBNode parent, RBNode sibling) {
	   if (sibling.color() != parent.color()){
		   flipColor(sibling);
	   }
	   if (parent.color() != "black") flipColor(parent);
	   if (sibling == parent.left()){
		   flipColor(sibling.left());
		   rotate("right", parent);
	   }
	   else {
		   flipColor(sibling.right());
		   rotate("left", parent);
	   }
   }
   
   /**
    * 
    *  private void deleteCase2rFix(RBNode parent, RBNode sibling)
    *  
    * sibling is set to red, parent to black.
    * 
    * Complexity - O(1).
    */
   private void deleteCase2rFix(RBNode parent, RBNode sibling) {
	   flipColor(parent);
	   flipColor(sibling);
   }
   
     
   /**
    * 
    * private void insertCase1Fix(RBnode newNode) {
    * 
    * Performs Case 1a and Case 1b fixes recursively.
    * 
    * precondition:
    * 	1. newNode is red
    * 	2. Uncle is red
    * postcondition: Tree has no case 1 errors
    * @param newNode
    * 
    * Complexity - O(logn)
    * 	1. Fixed set of changes O(1)
    * 	2. recursive call for fixing the parent - O(logn) - up to tree height
    * 
    */
   private void insertCase1Fix(RBNode newNode) {
	   flipColor(newNode.parent());
	   RBNode grandParent = newNode.parent().parent();
	   RBNode parent = newNode.parent();
	   
	   if (grandParent.left() == parent){ //parent is a left child
		   flipColor(grandParent.right()); //flip parent's sibling color
	   }
	   else {
		   flipColor(grandParent.left()); //flip parent's color
	   }
	   if (grandParent.parent() == dRoot) { //we got to the root, we're done
		   return;
	   }
	   
	   flipColor(grandParent);
	   if (grandParent.parent().color() == "black") { //grandparent's parent is black, we're done
		   return;
	   }
	   
	   dispatchFixInsert(identifyFixInsert(grandParent), grandParent); //re-run the fix dispatcher on the grandparent.
	   //might run all the way up the tree.
   }
   
   
   /**
    * 
    * identifies if the case after insertion is 1, 2 or 3
    * from the presentation.
    * 
    * @param newNode is the node added.
    * 
    * returns case number.
    * 
    * Complexity - O(1)
    * Fixed set of conditions to check.
    * 
    */
   
   private int identifyFixInsert(RBNode newNode){
	  RBNode grandParent = newNode.parent().parent();
	  RBNode parent = newNode.parent();
	  
	  if (parent == grandParent.left()){ //node's parent is a left child
		  if (grandParent.right().color() == "red") { //case 1 preconditions 
			  return 1;
		  }
		  else if (parent.right == newNode) { //case 2 preconditions
			  return 2;
		  }
		  else return 3; //case 3 preconditions
	  } else { //node's parent is a right child
		  if (grandParent.left().color() == "red") { //case 1 preconditions
			  return 1;
			  } else if (parent.left() == newNode) { //case 2 preconditions
		  return 2;
	  } //case 3 preconditions
	  return 3;
	  }
   }
   
   
   /**
    * activates the appropriate fix when a new node is inserted
    * 
    * 
    * @param i
    * @param newNode
    * 
    * Complexity - O(log(n)):
    * - complexity of insertCase1Fix is O(log(n)).
    * - complexity of insertCase2Fix and insertCase3Fix is O(1).
    */
   private void dispatchFixInsert(int i, RBNode newNode){
	   if (i == 1) insertCase1Fix(newNode);
	   if (i == 2) insertCase2Fix(newNode);
	   if (i == 3) insertCase3Fix(newNode);
   }
   
   /**
    * 
    * private void insertCase2Fix(RBnode newNode) 
    * 
    * Performs Case 2 fix
    * 
    * precondition:
    * 	1. Tree has no Case 1 errors
    * 	2. newNode is red
    * 	3. Dad is red
    * 	4. Uncle is black
    * 	5. newNode is on the closer to uncle side
    * postcondition: Tree is ready for Case 3 fix
    * 
    * Complexity:
    * One rotation and case 3 fix on the parent - O(1) + O(1) = O(1)
    * 
    */
   private void insertCase2Fix(RBNode newNode) {
	   RBNode parent = newNode.parent();
	   if (isParentALeftChild(newNode)) { //newNode's parent is a left child
		   rotate("left", newNode.parent()); //Left rotate on newNode's parent
	   } else { //newNode's parent is a right child
		   rotate("right", newNode.parent()); //Right rotate on newNode's parent
	   }
	   insertCase3Fix(parent);
   }
   
   /**
    * 
    * private void insertCase3Fix(RBnode newNode) 
    * 
    * Performs Case 3 fix
    * 
    * precondition:
    * 	1. Tree has no Case 1 and Case 2 errors
    * 	2. newNode is red
    * 	3. Dad is red
    * 	4. Uncle is black
    * 	5. newNode is on the far side of uncle
    * postcondition: Tree is valid
    * 
    * Complexity:
    * Two color flips and one rotation - O(1)
    * 
    */
   private void insertCase3Fix(RBNode newNode) {
	   
	   flipColor(newNode.parent());
	   
	   flipColor(newNode.parent().parent());
	   
	   if (isParentALeftChild(newNode)) { //newNode's parent is a left child
		   rotate("right", newNode.parent().parent()); //Right rotate on newNode's grandparent
	   } else { //newNode's parent is a right child
		   rotate("left", newNode.parent().parent()); //Left rotate on newNode's grandparent
	   }
   }
   
   /**
    * public addNode(RBNode father)
    * 
    * Inserts a new RBNode with the key i as a son of father.
    * Returns a pointer to the newly added node.
    * 
    * precondition: father exists in the tree
    * postcondition: none
    * 
    * Complexity - O(1)
    * 
    */
   private RBNode addNode(int i, RBNode father) {
	   RBNode node = new RBNode(i, father);
	   if (father.key() > i) {
		   father.setLeft(node);
	   }
	   else {
		   father.setRight(node);
	   }
	   
	   return node;
   }
   
   /** 
    * private boolean isPartentALeftChild(RBNode node)
    * 
    * Returns true is the node's parent is a left child, false otherwise.
    * 
    * precondition: node isn't tree root
    * postcondition: none
    * 
    * Complexity - O(1)
    * 
    */
   private boolean isParentALeftChild(RBNode node) {
	   RBNode parent = node.parent();
	   RBNode grandparent = parent.parent();

	   if (parent.key() < grandparent.key()) { //parent's key is smaller than his parent's key, meaning it's a left son
		   return true;
	   } else { //parent is a right son
		   return false;
	   }
   }
  

   /**
    * @param node
    * flips the color of the node.
    * updates the color flip counter.
    * 
    * Complexity - O(1)
    * 
    */
   private void flipColor(RBNode node){
	   if (node.color().equals("black")) { //change to red if current color is black
		   node.setColor("red");
	   }
	   else if (node.color().equals("red")) { //change to black if current color is red
		   node.setColor("black");
	   }
	   cnt++; //increase color flips counter
   }
   
  /**
   * public class RBNode
   * 
   * If you wish to implement classes other than RBTree
   * (for example RBNode), do it in this file, not in 
   * another file 
   *  
   */
  public class RBNode{
	  
	  private Double key = -1.0;
	  private RBNode left = RBTree.this.nil;
	  private RBNode right = RBTree.this.nil;
	  private RBNode parent = RBTree.this.nil;
	  private String color = "black";
	  
	  
	  public RBNode(){
	  }
	  
	  private RBNode(double d){
		  key = d;
	  }
	  
	  private RBNode(int i, RBNode father){
		  key = (double) i;
		  parent = father;
		  if (father == dRoot) color = "black";
		  else color = "red";   //new nodes are always red, except for the 1st one.
	  }
	  
	  
	  private int key(){
		  int k = (int) Math.floor(key);
		  return k;
	  }
	  
	  private void setKey(int k){
		  key = (double) k;
	  }
	  
	  private RBNode left(){
		  return left;
	  }
	  
	  private void setLeft(RBNode node){
		  left = node;
	  }
	  
	  private RBNode right(){
		  return right;
	  }
	  
	  private void setRight(RBNode node){
		  right = node;
	  }
	  
	  private RBNode parent(){
		  return parent;
	  }
	  
	  private void setParent(RBNode node){
		  if (key == -1.0) return;  //writing to NULL.parent is harmless.
		  parent = node;
	  }
	  
	  private String color(){
		  return color;
	  }
	  
	  private void setColor(String col){
		  color = col;
	  }
}
  
}
  
  /**
 * @original author Shai Vardi
 * Modified for semester 2012/2013 a
 */

